Constraint bipartite vertex cover: simpler exact algorithms and implementations
Identifieur interne : 000864 ( Main/Exploration ); précédent : 000863; suivant : 000865Constraint bipartite vertex cover: simpler exact algorithms and implementations
Auteurs : Guoqiang Bai [Allemagne] ; Henning Fernau [Allemagne]Source :
- Journal of combinatorial optimization [ 1382-6905 ] ; 2012.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
CONSTRAINT BIPARTITE VERTEX COVER is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations. We also discuss possible generalizations and enhancements.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000278
- to stream PascalFrancis, to step Curation: 000A52
- to stream PascalFrancis, to step Checkpoint: 000219
- to stream Main, to step Merge: 000887
- to stream Main, to step Curation: 000864
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Constraint bipartite vertex cover: simpler exact algorithms and implementations</title><author><name sortKey="Bai, Guoqiang" sort="Bai, Guoqiang" uniqKey="Bai G" first="Guoqiang" last="Bai">Guoqiang Bai</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Abteilung Informatik, Univ. Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Univ. Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Abteilung Informatik, Univ. Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Univ. Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">12-0332188</idno><date when="2012">2012</date><idno type="stanalyst">PASCAL 12-0332188 INIST</idno><idno type="RBID">Pascal:12-0332188</idno><idno type="wicri:Area/PascalFrancis/Corpus">000278</idno><idno type="wicri:Area/PascalFrancis/Curation">000A52</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000219</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000219</idno><idno type="wicri:doubleKey">1382-6905:2012:Bai G:constraint:bipartite:vertex</idno><idno type="wicri:Area/Main/Merge">000887</idno><idno type="wicri:Area/Main/Curation">000864</idno><idno type="wicri:Area/Main/Exploration">000864</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Constraint bipartite vertex cover: simpler exact algorithms and implementations</title><author><name sortKey="Bai, Guoqiang" sort="Bai, Guoqiang" uniqKey="Bai G" first="Guoqiang" last="Bai">Guoqiang Bai</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Abteilung Informatik, Univ. Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Univ. Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Abteilung Informatik, Univ. Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Univ. Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></analytic><series><title level="j" type="main">Journal of combinatorial optimization</title><title level="j" type="abbreviated">J. comb. optim.</title><idno type="ISSN">1382-6905</idno><imprint><date when="2012">2012</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Journal of combinatorial optimization</title><title level="j" type="abbreviated">J. comb. optim.</title><idno type="ISSN">1382-6905</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Combinatorial optimization</term><term>Constraint</term><term>Formalization</term><term>Graph covering</term><term>Graph theory</term><term>Reconfigurable architectures</term><term>Resource allocation</term><term>Simplification</term><term>Vertex(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Optimisation combinatoire</term><term>Contrainte</term><term>Sommet graphe</term><term>Théorie graphe</term><term>Formalisation</term><term>Allocation ressource</term><term>Simplification</term><term>Recouvrement graphe</term><term>Architecture reconfigurable</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">CONSTRAINT BIPARTITE VERTEX COVER is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations. We also discuss possible generalizations and enhancements.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><noRegion><name sortKey="Bai, Guoqiang" sort="Bai, Guoqiang" uniqKey="Bai G" first="Guoqiang" last="Bai">Guoqiang Bai</name></noRegion><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000864 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000864 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:12-0332188
|texte= Constraint bipartite vertex cover: simpler exact algorithms and implementations
}}
| This area was generated with Dilib version V0.6.31. |  |